package tree;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @author kaho
 * @since 2021/2/28
 */
public class _145_二叉树的后序遍历 {

    public List<Integer> postorderTraversal1(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root==null) {
            return result;
        }
        LinkedList<TreeNode> stack1 = new LinkedList<>();
        LinkedList<TreeNode> stack2 = new LinkedList<>();
        stack1.add(root);
        while (!stack1.isEmpty()) {
            int size = stack1.size();
            for (int i = 0; i < size; i++) {
                TreeNode pop = stack1.pop();
                stack2.push(pop);

                if (pop.left != null) {
                    stack1.push(pop.left);
                }
                if (pop.right!=null) {
                    stack1.push(pop.right);
                }
            }
        }
        for (TreeNode treeNode : stack2) {
            result.add(treeNode.val);
        }
        return result;
    }









    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root==null) {
            return result;
        }
        LinkedList<TreeNode> stack1 = new LinkedList<>();
        LinkedList<TreeNode> stack2 = new LinkedList<>();
        stack1.push(root);
        while (!stack1.isEmpty()){
            TreeNode pop = stack1.pop();
            stack2.push(pop);
            if (pop.left!=null) {
                stack1.push(pop.left);
            }
            if (pop.right!=null) {
                stack1.push(pop.right);
            }
        }

        while (!stack2.isEmpty()) {
            result.add(stack2.pop().val);
        }
        return result;
    }
}
